#include <util.h>

void shell_insert(int a[], int n, int dk)
{
    int i, j, x;

    for (i = dk; i < n; i++)
    {
        x = a[i];
        for (j = i - dk; j >= 0 && a[j] > x; j -= dk)
            a[j+dk] = a[j];
        a[j+dk] = x;
    }
}

/*
 * what delta[m] should be look like?
 * All deltas have no common divisor except 1, and the last delta must be 1.
 */
void shell_sort(int a[], int n, int delta[], int m)
{
    int i;

    for (i = 0; i < m; i++)
        shell_insert(a, n, delta[i]);
}

void insert_sort(int a[], int n)
{
    int i, j, x;

#if 0
    for (i = 1; i < n; i ++)
    {
        x = a[i];
        for (j = i-1; j >= 0 && a[j] > x; j--)
            a[j+1] = a[j];
        a[j+1] = x;
    }
#else
    for (i = 1; i < n; ++i)
    {
        // check to avoid two assignments when a[i-1] <= a[i];
        if (a[i-1] <= a[i])
            continue;
        x = a[i];
        a[i] = a[i-1];
        for (j = i-2; j >= 0 && a[j] > x; j--)
            a[j+1] = a[j];
        a[j+1] = x;
    }
#endif
}

void binary_insert_sort(int a[], int n)
{
    int x, i, j, low, high, mid;

    for (i = 1; i < n; i ++)
    {
        x = a[i];
        low = 0;
        high = i - 1;
        while (low <= high)
        {
           mid = (low + high) / 2;
           if (x > a[mid])
               low = mid + 1;
           else
               high = mid - 1;
        }
        // low = high+1; store x in a[low]
        for (j = i-1; j >= low; j--)
            a[j+1] = a[j];
        a[low] = x;
    }
}

int main()
{
    int i;
    int a[8], delta[4] = {5, 3, 2, 1};

    srand(time(NULL));
    for (i = 0; i < 8; i++)
        a[i] = rand() % 100;

    print_a(a, 8, NULL);

    // insert_sort(a, 8);
    // binary_insert_sort(a, 8);
    shell_sort(a, 8, delta, 4);

    print_a(a, 8, NULL);

    return 0;
}
